package com.huangyi;

public class Main {
    public static void main(String[] args) {
        // 测试用例
    }

    // 买卖股票的最佳时机 III
    static class Solution {
        public int maxProfit(int[] prices) {
            int m = prices.length;
            int[][] f = new int[m + 1][3]; // 持有股票
            int[][] g = new int[m + 1][3]; // 不持有股票

            // 初始化：第0天持有股票是不可能的状态
            f[0][0] = Integer.MIN_VALUE / 2;
            f[0][1] = Integer.MIN_VALUE / 2;
            f[0][2] = Integer.MIN_VALUE / 2;

            g[0][0] = 0; // 初始不持有、无交易
            g[0][1] = Integer.MIN_VALUE / 2;
            g[0][2] = Integer.MIN_VALUE / 2;

            for (int i = 1; i <= m; i++) {
                for (int j = 0; j < 3; j++) {
                    // 今天持有 = max(昨天就持有, 昨天不持有今天买入)
                    f[i][j] = Math.max(f[i-1][j], g[i-1][j] - prices[i-1]);

                    // 今天不持有 = 昨天就不持有（默认）
                    g[i][j] = g[i-1][j];

                    // 或者昨天持有今天卖出（交易次数+1）
                    if (j >= 1) {
                        g[i][j] = Math.max(g[i][j], f[i-1][j-1] + prices[i-1]);
                    }
                }
            }

            // 最后一天取所有状态的最大值
            int cur1 = Math.max(g[m][2], Math.max(g[m][0], g[m][1]));
            return cur1;
        }
    }

    // 买卖股票的最佳时机 IV
    static class Solution2 {
        public int maxProfit(int k, int[] prices) {
            int m = prices.length;
            int[][] f = new int[m + 1][k + 1]; // 持有股票
            int[][] g = new int[m + 1][k + 1]; // 不持有股票

            // 初始化：第0天持有股票是不可能的状态
            for (int i = 0; i <= k; i++) {
                f[0][i] = Integer.MIN_VALUE / 2;
            }
            // 初始化：第0天不持有股票且未交易
            for (int i = 0; i <= k; i++) {
                g[0][i] = (i == 0) ? 0 : Integer.MIN_VALUE / 2;
            }

            // 状态转移
            for (int i = 1; i <= m; i++) {
                for (int j = 0; j <= k; j++) {
                    // 今天持有 = max(昨天就持有, 昨天不持有今天买入)
                    f[i][j] = Math.max(f[i-1][j], g[i-1][j] - prices[i-1]);

                    // 今天不持有 = 昨天就不持有（默认）
                    g[i][j] = g[i-1][j];

                    // 或者昨天持有今天卖出（交易次数+1）
                    if (j >= 1) {
                        g[i][j] = Math.max(g[i][j], f[i-1][j-1] + prices[i-1]);
                    }
                }
            }

            // 最后一天不持有股票的所有交易次数中取最大值
            int result = 0;
            for (int i = 0; i <= k; i++) {
                result = Math.max(result, g[m][i]);
            }
            return result;
        }
    }
}